package string.leetcode.hard;

/**
 * @author bruin_du
 * @description 含有所有字符的最短字符串
 * @date 2022/8/8 23:26
 **/
public class OfferII017_MinWindow {
    public String minWindow(String s, String t) {
        int lenS = s.length(), lenT = t.length();
        if (lenS < lenT) return "";
        int left = 0, right = 0,resLen = Integer.MAX_VALUE;
        //用于判断字符串匹配中还有几个字符不匹配
        //也就是arrS有几个字母还比arrT少
        int flag = 0;
        String res = "";
        int[] arrS = new int[58], arrT = new int[58];
        for (int i = 0; i < lenT; i++) {
            ++arrT[t.charAt(i) - 'A'];
        }
        for (int i = 0; i < arrT.length; i++) {
            if (arrT[i] > 0) flag++;
        }
        while (right < lenS) {
            int index = s.charAt(right) - 'A';
            arrS[index]++;
            if (arrS[index] == arrT[index]) flag--;

            //所有字母都大等于了
            while (flag == 0) {
                if (resLen > right - left + 1) {
                    res = s.substring(left, right + 1);
                    resLen = res.length();
                }

                int x = s.charAt(left) - 'A';
                arrS[x]--;
                if (arrT[x] != 0 && arrS[x] < arrT[x]) {
                    flag++;
                }
                left++;
            }
            right++;
        }
        return res;
    }

    public static void main(String[] args) {
        OfferII017_MinWindow offer = new OfferII017_MinWindow();
        System.out.println(offer.minWindow("ab", "b"));
    }
}
